算法 - BitMap 求QQ号的交集

A 文件有 30 亿个 QQ 号码，B 文件有 40 亿个 QQ 号码，求 A 文件和 B 文件中 QQ 号码的交集，内存大小限制为 1GB。

一. 直接暴力比较

最简单的方法是直接暴力比较，如下：

显然，这种方法要比较的次数是：30 亿*40 亿，时间复杂度太大了，无法通过腾讯面试。

既然时间复杂度不符合要求，那就要反思一下暴力比较的算法了，显然，应该用哈希表，优化查找速度，如下：

显然，时间复杂度大大降低，只需要遍历上面一层即可。然而，空间的占用还是太大了，1GB 的内存根本无法容纳 40 亿个 QQ 号。

既然内存容纳不下，那就想办法进行切割吧，比如：根据 QQ 号码的最后一位的值来切割 A 文件和 B 文件，使文件变小。显然，尾数为 j 的 QQ 号码只可能在 Aj 文件和 Bj 文件中，只需要比较 Aj 和 Bj 文件即可。

| QQ 号最后一位
| A 文件的切割
| B 文件的切割 |
| 0
| A0
| B0 |
| 1
| A1
| B1 |
| 2
| A2
| B2 |
| 3
| A3 | B3 |
| ...
| ...
| ...
|

通过切割的方法，可以化大为小，让内存容纳得下，对应的图示如下：

需要强调的是，仅仅以 QQ 号最后一位来划分，那么每个小文件的数据量大约是原来文件的 1/10, 可能还是偏大，怎么办？

可以考虑以 QQ 号的最后 3 位来划分，那么每个小文件的数据量大约是原来大文件的 1/1000，甚至还可以更细地来进行划分。

通过一定的规则进行分割，把 A 文件和 B 文件中同类型数据划分到对应的小文件中，解决了内存问题，能勉强通过腾讯面试。

我们回头看一下，要么是时间不符合要求，要么是空间不符合要求，那有没有时间和空间都符合要求的数据结构呢？

显然有的！我们可以对 hashmap 进行优化，采用 bitmap 这种数据结构，可以顺利地同时解决时间问题和空间问题。

在很多实际项目中，bitmap 经常用到。我看了不少组件的源码，发现很多地方都有 bitmap 实现，bitmap 图解如下：

这是一个 unsigned char 类型，可以看到，共有 8 位，取值范围是[0, 255]，如上这个 unsigned char 的值是 255，它能标识 0~7 这些数字都存在。

同理，如下这个 unsigned char 类型的值是 254，它对应的含义是：1~7 这些数字存在，而数字 0 不存在：

由此可见，一个 unsigned char 类型的数据，可以标识 0~7 这 8 个整数的存在与否。以此类推：

显然，可以推导出来：512MB 大小足够标识所有 QQ 号码的存在与否，请注意：QQ 号码的理论最大值为 2^32 - 1，大概是 43 亿左右。接下来的问题就很简单了：

用 512MB 的 unsigned int 数组来记录 B 文件中 QQ 号码的存在与否，形成一个 bitmap. 然后遍历 A 文件中的 QQ, 看是否在 bitmap 中，如果在，那么该 QQ 号码就同时存在于 A 和 B 两个文件中。

bitmap 非常巧妙，这种方式能通过腾讯的面试。当时我在腾讯终面时时遇到了这个题目，先简要指明了为什么 1 和 2 方法不行，然后给出了 3 和 4 中的方法，并说明了 3 和 4 的优缺点，万事大吉。

bitmap 很重要，也是经常涉及到的考点，不能不掌握。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。